#include <stdio.h>
#include <stdlib.h>

struct node {
	int value;
	struct node* right;
	struct node* left;
};
typedef struct node node;

node * NewNode()
{
	node * tmp;
	tmp = malloc(sizeof(node));
	if (tmp == NULL) {
		printf("Error allocating memory\n");
	}
	tmp->right = tmp->left = NULL;
	return tmp;
}

void InsertNode (struct node **node_ptr,int value)
{
  struct node *node = *node_ptr;
  if (node == NULL) {
    *node_ptr = NewNode();
	(*node_ptr)->value = value;
  }
  else if (node->value <=  value)
    InsertNode (&node->right, value);
  else
    InsertNode (&node->left, value);
}

void freeTree(node* root)
{
	if (root != NULL ) {
		freeTree(root->left);
		free(root->left);
		freeTree(root->right);
		free(root->right);
	}	
}

void preOrderTraverse(node* root)
{
	if( root != NULL) {
		printf("%d ", root->value);
		preOrderTraverse(root->left);
		preOrderTraverse(root->right);
	}
}

int validateBSTree(node* root)
{
	int left, right;
	if ( root != NULL) {
		if (root->left)
			left = root->value > validateBSTree(root->left) ;
		else 
			return root->value;
		if (root->right)
			right = root->value <= validateBSTree(root->right);
		else 
			return root->value;
		printf(" Val %d\n",left && right);
	}
}

int calcHeight(node* root)
{
	int htl, htr;

	if (root != NULL) {
		htl = calcHeight(root->left);
		htr = calcHeight(root->right);
		printf("HTL=%d, HTR=%d\n",htl, htr);
		return (htl>htr?htl:htr)+1;
	} else {
		return -1;
	}
}

int main()
{
	node *root;
	int result = 0;
	root=NULL;

	InsertNode(&root, 10);
	InsertNode(&root, 11);
	InsertNode(&root, 15);
	InsertNode(&root, 16);
	InsertNode(&root, 17);
	InsertNode(&root, 18);
	InsertNode(&root, 19);
	InsertNode(&root, 9);
	InsertNode(&root, 8);
	InsertNode(&root, 10);
	InsertNode(&root, 10);
	InsertNode(&root, 7);
	InsertNode(&root, 2);
	InsertNode(&root, 15);
	InsertNode(&root, 3);
	preOrderTraverse(root);

	printf("Result = %d\n", calcHeight(root));
	printf("Result = %d\n", validateBSTree(root));
	freeTree(root);
	free(root);

	return 0;
}
